Testing The Uniformity Conjecture

Daniel Richardson, Computer Science, Bath University, Bath BA2 7AY, UK email: masdr@bath.ac.uk

May 2, 2002

Abstract

The uniformity conjecture postulates a relationship between the syntactic length of expressions built up from the natural numbers using field operations, radicals and exponentials and logarithms, and the smallness of non zero complex numbers defined by such expressions. The Uniformity Conjecture claims that if the expressions are written in an expanded form in which all the arguements of the exponential function have absolute value bounded by 1, then a small multiple of the syntactic length gives a bound for the number of decimal places needed to distinguish the defined number from zero. The problem of searching for a counterexample is discussed. All values of expressions of length 5 are generated and their distributions are described. Use of continued fractions to find good rational approximations to irrational real numbers is discussed. The first 200 partial quotients are computed for expressions of the form n^{1/m}, log(n)^{1/m}, log(n) ∗ log(m), log(n/m), log(n + log(m)), exp(n/(n + m)), log(n) ∗ exp(1/m) for all integral n and m between 2 and 100. Use of the LLL algorithm and the PSLQ algorithm to look for counterexamples among linear forms is briefly discussed. No counterexamples are found.

1 Introduction

The nested radical and exponential-logarithmic expressions are, roughly speaking, those which can be constructed from expressions for natural numbers using the operators \{+, −, ∗, /, \sqrt[n]{,} exp, log\}.

In the section below, the family of nested radical exponential-logarithmic expressions, (exp-log expressions for short), is described and the field of closed form numbers is defined. An expanded form is defined for the explog expressions, and the Uniformity Conjecture is stated. This claims that for expressions in expanded form, a small multiple of the syntactic length bounds the number of decimal places needed to distinguish the defined number from zero, if it is non zero.

The Uniformity Conjecture is compared with some known results about approximation. In the next section all expressions up to length 5 are examined, and it is shown that such a short counterexple does not occur. Finally, use of continued fractions, the LLL algorithm and the PSLQ algorithm, in order to search for counterexamples among linear forms with integral coefficients, is discussed.

2 Closed Form Numbers and the Uniformity Conjecture

2.1 Expressions

We assume, to begin with, some canonical representation for the natural numbers. Then the set of nested radical exponential and logarithmic expressions is the smallest set of expressions so that:

1. All the representations of natural numbers are in the set.

2. If A and B are in the set so are (A + B), (A − B), and (A ∗ B), (A/B).

3. If A is in the set, so are −A, exp(A) and log(A)

4. If A is in the set and n is a canonical representation of a natural number bigger than 1, then A^{1/n} is in the set.

Each nested radical exponantial and logarithmic expression E is either undefined, or is interpreted as a real or complex number V (E), as follows.

1. If E is a representation of an natural number, V (E) is that integer.

2. The operators are given the usual precedence in the absence of brackets.

3. If A and B are defined, then V (A + B), V (A − B), V (A ∗ B) and V (−A) are defined with the usual interpretation of the operators. If B is defined, and V (B) is not zero, then V (A/B) is defined, with the usual interpretation.

4. If A is defined, then exp(A) is defined with meaning e^{A}.

5. If A is defined, and V (A) ≠ 0, then log(A) is defined, as the branch of the logarithm base e so that −π < ImaginaryP art(log(A)) ≤ π.

6. If A is defined and and V (A) ≠ 0, then A^{1/n} is defined and equal to exp(log(A)/n).

The operator V is called evaluation.

The complex numbers defined in this way are called closed form ([Chow 1999]). A field with good closure properties including the closed form numbers

is the field of elementary numbers. These are numbers of the form q(α), where q is in Q Q Q[x_{1}, …, x_{n}], and α ∈ C C C^{n} is a non singular solution of a system of equations (p_{1}, …, p_{n}) = 0 and each p_{i} is in Z[x_{1}, …, x_{n}, e^{x_{1}}, …, e^{x_{n}}]. It has been shown that this is an effective field if the Schanuel conjecture is true. See [Richardson 1997], [Richardson 2001].

Please notice that although we have expressions here for n th roots, we do not have expressions for n th powers. If we want A^{2}, for example, we have to write it as A ∗ A.

2.2 Length of an expression

Our set of nested radical exponential and logarithmic expressions depends on a choice of canonical representation for the natural numbers. Assume that we have chosen some base b for representation of the natural numbers. We define the length of an natural number in this representation to be the number of digits base b which are used.

We may view expressions as trees which have natural numbers at the frontier and have operators at the interior nodes. We define the length of a nested radical exponential and logarithmic expression by the following:

length(A + B) = length(A) + length(B) + 1

length(A − B) = length(A) + length(B) + 1

length(−A) = length(A) + 1

length(A ∗ B) = length(A) + length(B) + 1

length(A/B) = length(A) + length(B) + 1

length(A^{1/n}) = length(A) + length(n) + 1

length(e^{A}) = length(A) + 1

length(log(A)) = length(A) + 1.

So, for example, in decimal notation, 4 − 3 ∗ (10)^{1/8} would have length 8, since it has 5 digits and 3 operator symbols. In general, the length counts the number of operators and the number of digits used.

2.3 Gap Functions

Definition 1. A gap function for the closed form numbers is a function g : Exp → R R R_{+}, where Exp is the set of nested radical exponential and logarithmic expressions, so that if x is a closed form number represented by an expression A, and x ≠ 0 then

|x| > 10^{−g(A)}

A gap function tells us the amount of decimal precision which is needed to distinguish a non zero number from zero. Of course gap functions exist. We hope that there is a computable gap function, and even an easily computable gap function.

We have a natural scale, i.e. length, on expressions; and we also have a natural scale, i.e. the logarithm of the absolute value, on the complex numbers. The central question of this article is: How does the evaluation operator, V, behave with respect to these two scales?

2.4 Uniformity Conjecture

Using iterated exponentiation, it is possible to define very large numbers. Since we have division, it is also possible to define very small numbers with expressions involving iterated exponentiation, followed by division. There does not seem to be any other way to get very large numbers, or very small non zero numbers. ( Note that although we allow nth roots, we do not have nth powers. So we can not easily write a short expression for the result of a sequence of repeated squarings, for example.)

We consider an expression E to be a subexpression of itself.

We will say that an expression E is in expanded form if for any exponential subexpression e^{A} of E, we have |V (A)| ≤ 1.

It appears to be true that it is not possible to define any very large numbers, or any very small non zero numbers using small expressions in expanded form. This somewhat vague idea led to the original statement of the uniformity conjecture, as given below. See [Richardson 2000] (which uses a slightly different definition of length).

Uniformity Conjecture: If E is an expression in expanded form, and V (E) ≠ 0, then |V (E)| is bigger than 1/N(k), where k is the length of E, and N(k) is the number of syntacticaly correct expanded form expressions of length ≤ k.

Expressions of length less than k can be coded as sequences of symbols of length k by padding with an initial sequence of right brackets. So the number of expressions of length not exceeding k is bounded by the number of sequences of length k. Therefore, if we have S symbols for operators and digits in our alphabet, the number of syntactically correct expressions of length ≤ k is bounded by S^{k}. In case we use decimal notation, for example, S would be 17. In binary notation, S would be 9.

Assuming decimal notation, 10^{k} < N(k) < 10^{1.24k}. Suppose k > 4. Consider a string of symbols of length k with digits on the ends, and digits at all the odd numbered positions and either digits or operators +, −, ∗, / at interior even numbered positions. There are 14 choices for symbols at these interior even numbered positions, and 10 choices for the others. Any such string is syntactically correct. So, assuming k > 4, we get 10^{1.04k} < N(k) < 10^{1.24k}.

Roughly speaking, the conjecture says that the amount of base S precision which is needed to discriminate the value of an expanded form expression from zero is proportional to the length of the expression.

The quantity N(k) is not very nice to work with. So, in the following, we will consider:

Modified Uniformity Conjecture: If E is an expression in expanded form, and using decimal notation for integers, and V (E) ≠ 0, then

−Log_{10}(|V (E)|) ≤ Ck

where k is the length of E, and C = Log_{10}(17).

Log_{10}(17) is about 1.24. The right hand side of the inequality is just the information content of the string E, viewed as a random element of the set of strings with the given alphabet.

We will say that a number occurs at level k if it has an exp-log expression representing it with length no more than k.

A weaker form of the uniformity conjecture may be obtained by replacing raising the constant C to some other value. A reason why at least this weaker form of the conjecture may seem plausible is that if a number α occurs at level j, then the neighbourhood of 0 at level k translates to a subset of neighbourhood of α at level k + j + 1, since if α is represented by expression A, and a number ϵ is represented by an expression E, then A + E will represent α + ϵ. Similarly, a neighbourhood of α at one level gets translated to a subset of a neighbourhood of 0 at a higher level; and so we would expect all the neighbourhoods of points, graded by level, to look alike, except for a change of scale.

The expressions I know which have small evaluations are not even close to being counterexamples. 4/3 − 10^{1/8} is zero to three decimal places; 7log2 − 3log5 is zero to 2 decimal places, for example. Even if we add π as a constant to our language, I still do not know a counterexample in the enlarged language. The famous 3 ∗ log(640320)/\sqrt{163} − π is only zero to 15 decimal places, whereas its syntactic length is 15 plus the length of π. We can replace

π = log(−1)/(−1)^{1/2}

in which case the length of π would be 8.

The Uniformity conjecture is related to a family of conjectures, called Witness conjectures, originating with Joris van der Hoeven. See [Van Der Hoeven 95], [Van Der Hoeven 97], [Van Der Hoeven 2000].

Note that we can replace any expression which defines a value by an equivalent one in expanded form. But this is unlikely to be a good way to decide zero equivalence over the set of all nested radical exponential and logarithmic expressions. Joris van der Hoeven ([Van Der Hoeven 95]) has suggested that expressions not in expanded form could be put into some sort of asymptotic form, as if the large numbers were exp-log functions which tended to infinity. I imagine that this is a good idea. For the rest of this article, however, we will just ignore expressions not in expanded form.

3 Computational Consequences

Real and complex numbers are not adequately represented by floating point numbers. A more sophisticated idea would be to attempt to compute with definitions of real and complex numbers, rather than with approximations. The main problem in this area is how to recognize that two definitions represent the same number. See [Richardson 1997], [Richardson 2001], [Pohst 1997]. This problem occurs in all computer algebra systems. The solution which is usually adopted in practice is to use approximations and to decide that if a number is sufficiently close to zero, it must actually be zero, or at least we hope not much harm will be done by assuming that it is zero. The uniformity conjecture, if true, gives a more principled way way of using this rough idea. See [Richardson 2000].

4 Diophantine Approximations

4.1 Liouville Estimate

Define the logarithmic height, h(p), of a polynomial p with integral coefficients to be the logarithm of the maximum of the absolute values of the coefficients. Define the logarithmic height of an algebraic number to be the logarithmic height of the minimal defining polynomial in Z Z Z[x]. We have:

Theorem 1. Liouville Estimate. Let ξ_{1}, …, ξ_{m} be algebraic numbers, of degrees d_{1}, …, d_{m} and logarithmic heights h_{1}, …, h_{m} respectively. Let d be the degree of the extension Q Q Q(ξ_{1}, …, ξ_{m}) over Q Q Q. Let P be a polynomial in Z Z Z[x_{1}, …, x_{m}], of degree N_{i} in x_{i}. If P (ξ_{1}, …, ξ_{m}) ≠ 0, then

−d(h(P) + ∑_{i=1}^{m}(N_{i}h_{i}/d_{i}) + 2N_{i}) ≤ log |p(ξ_{1}, …, ξ_{m})|

For proof, see [Lang 1966].

4.2 Examples

Consider a linear form in radicals.

λ = b_{1}(a_{1})^{1/n_{1}} + b_{2}(a_{2})^{1/n_{2}} + ⋯ + b_{k}(a_{k})^{1/n_{k}} + b_{k+1}, with b_{i} ∈ Z Z Z, and n_{i}, a_{i} positive natural numbers for all i. Assume λ ≠ 0. Then we get the following contrasting estimates. (Note that logarithms here are base 2.)

1. Liouville Estimate.

log |λ| ≥ −(∏ n_{i})(logMax_{i}(|b_{i}|) + ∑_{i} log(|a_{i}|)/n_{i} + 2k)

2. Uniformity Conjecture. log |λ| ≥ −C(∑ log |n_{i}| + ∑ log |a_{i}| + ∑ log |b_{i}| + 3k), where C ≤ log(19).

The most striking feature of the above is that in the Liouville estimate the precision needed increases as the product of the radical degrees; but according to the uniformity conjecture all that is needed is the sum of the logarithms. Thus even in this simple algebraic case, the uniformity conjecture would imply quite strong new results.

4.3 Baker-Waldschmidt

See [De Weger 1987].

Theorem 2. (Baker-Waldschmidt) Suppose p_{1}, …, p_{n} ∈ Z Z Z with 2 ≤ p_{1} < ⋯ < p_{n} and that (Q Q Q(p_{1}^{1/2}, …, p_{n}^{1/2}) : Q Q Q) = 2^{n}. Let b_{1} …, b_{n} ∈ Z Z Z, with B = Max_{1≤i≤n} |b_{i}|. Suppose λ = b_{1}logp_{1} + ⋯ + b_{n}logp_{n} ≠ 0. Let V_{i} = Max(1, logp_{i}), for i = 1, …, n. Let ω = V_{1} … V_{n}. Let

C_{1} = 2^{9n+26}n^{n+4}ωlog(eV_{n−1}

C_{2} = C_{1}log(eV_{n})

Then

|λ| > e^{−(C_{1}logB+C_{2})}.

This should be compared with the uniformity conjecture, which predicts:

|λ| > 19^{−(∑ length(p_{i})+length(b_{i})+2n−1)}

In this case, the most striking difference is that the coefficient C_{1} in the Baker-Waldschmidt result increases as the product of the lengths of the p_{i}, whereas in the prediction from the uniformity conjecture, only the sum of the lengths appears.

Patrice Philippon relates a similar lower bound on linear forms in logarithms with the abc conjecture. See [Philipon 1999], [Philipon 2000].

4.4 Thue-Siegel-Roth

See [Hindry and Silverman 2000], [Sprindzhuk 1980].

Theorem 3. (Thue-Siegel-Roth) For any algebraic number α and for any δ > 0

|p/q − α| > q^{−(2+δ)}

for all but finitely many (p/q) in Q Q Q.

The uniformity conjecture would predict that if A is an expression representing α then:

|p/q − α| > 1/N(k), where k is the length of p/q−A, ie k = length(p)+ length(q) + length(A) + 2)

provided α ≠ p/q. In this case the inequality directly implied by the uniformity conjecture is weaker than that of Thue-Siegel-Roth, but does not allow exceptions. So even in this case, the uniformity conjecture would imply new results. On the other hand, the Thue-Siegel-Roth theorem implies a bound on the number of counterexamples to the uniformity conjecture of the form α − p/q, for fixed algebraic closed form α.

Schmidt has extended the above result to the case of linear forms with integral coefficients in any number of algebraic numbers. See [Baker 1975].

Theorem 4. (Schmidt)For any algebraic numbers α_{1}, …, α_{n} with 1, α_{1}, …, α_{n} linearly independent over the rationals, and for any δ > 0, there are at most finitely many positive integers q so that

|q_{1}α_{1} + ⋯ + q_{n}α_{n} − p| < q^{−n−δ}

where q − Max(|q_{i}| , i = 1, …, n).

5 Search for a Counterexample to the Uniformity Conjecture

Let E range over expressions in expanded form, with V (E) ≠ 0. The modified uniformity conjecture states that

Sup{−Log_{10}(|V (E)| /length(E)} ≤ Log_{10}(17).

Even if we do not believe this is plausible, we would like either to show that this quantity is unbounded or to find a good upper bound for it.

Define R(E) = Log_{10} |V (E)| /length(E). Let ρ(E) = |R(E)|.

Definition 2. We will say that an expression E is dominant if E is in expanded form, V (E) ≠ 0, and ρ(E) ≥ ρ(D) for all D with length(D) ≤ length(E).

We will define ρ^{∗}(k) to be the supremum of ρ(E) for E of length ≤ k, and, as usual, E in expanded form and V (E) ≠ 0. So, for example, ρ^{∗}(1) = Log_{10}(9) and ρ^{∗}(2) = (1/2)Log_{10}(99). In general, ρ^{∗}(k) ≥ (1/k)Log_{10}(10^{k} − 1).

It is easy to establish the following.

Lemma 1. 1. 10^{−ρ(k)k} ≤ |V (E)| ≤ 10^{ρ(k)k}, where E is in expanded form of length no more than k and V (E) ≠ 0

2. Expressions of the following form are not dominant: e^{A}, −A, 1/A, A∗ B, A/B, A^{1/n}.

Proof.

Since ρ(E) = |Log_{10} |V (E)| /length(E)|,

10^{−ρ(E)length(E)} ≤ absV (E) ≤ 10^{ρ(E)length(E)}, and so the first part follows. The second part is equally easy. e^{A} is not dominant, since dominant expressions have to be in expanded form. A ∗ B is not dominant since

ρ(A ∗ B) = |Log_{10} |V (A)V (B)| /(length(A) + length(B) + 1)| and this is less than the maximum of ρ(A) and ρ(B). □ So the only possibilities for dominant expressions are natural numbers

and expressions of the form Log(A), A+B, A−B. Also, if E is dominant, and not an integer, it is so by being small, rather than large. That is,

|V (E)| < 10^{−ρ^{∗}(k−1)k}

where k is the length of E.

The supremum of ρ(E) is clearly at least 1. According to the modified uniformity conjecture, this supremum is no more than Log_{10}(17). It seems plausible that there could be dominant expressions which are not just strings of nines, and that there are expressions E with ρ(E) > 1. Such expressions are shown to exist later. However they were not encountered in the initial investigation.

5.1 All values up to length k

Let E_{k} be the number of expressions of length k. Let N_{k} be the number of natural numbers of length k. Let B_{k} be the number of expressions of length k of the form (A opB), where op ∈ {+, −, ∗, /}. Let U_{k} be the number of expressions of length k of the form op(A), where op ∈ {−, exp, Log}. Let R_{k} be the number of expressions of length k of the form A^{1/n}, where n is a canonical form natural number at least 2. We then have:

E_{k} = N_{k} + B_{k} + U_{k} + R_{k}

B_{k} = ∑_{i=1}^{k−2} 4E_{i} ∗ E_{k−i−1}

U_{k} = ∑_{i=1}^{k−1} 3E_{i}

R_{k} = (N_{1} − 2) ∗ E_{k−2} + ∑_{i=2}^{k−2} N_{i} ∗ E_{k−i−1}

Using the same recursive pattern, it is possible to generate a list of all expressions of any given length. This was originally done, in C, for expressions of length 5 and 6, by Marc Barniol Colom, a visiting student from Barcelona, as part of his final year project.

There is a basic methodological problem here. We hope to use the uniformity conjecture to help us solve the identity problem for exp log constants. However, in the absence of a solution to this problem, how can we be sure we know whether or not an expression is defined or whether or not it is in expanded form? At the beginning of this line of investigation, as part of his final year project, Marc Colom attempted to identify expressions which evaluated to zero by evaluating them with precision 15, and then checked expressions which seemed to be zero by sending them to Maple and reevaluating them with precision 100. This was done for level 5 and level 6 expressions. Since no anomolies were found in this way, the result, after Marc Colom’s work, was that if there was such a short counterexample, it must be an extreme one.

It seemed that instead of first generating the big list of expressions and then trying to process it, it might be best to do everything inside some computer algebra system, and to write a procedure Ex(k, i) which computes the i^{th} expression of length k if this is defined and in expanded form, and otherwise returns SKIP. Inside a computer algebra system it ought, hopefully, to be possible, at least for short expressions, to prove that every expression encountered which seems to be zero was actually exactly zero.

A very cautious (and time consuming) approach eventually prevailed. Everything was done inside Maple, with many checks. Only expressions of length 5 were done. If an expression 1/E or Log(E) was being considered, the absolute value of V (E) would first be computed as a floating point number. If V (E) seemed to be possibly zero, the simplify routine of Maple was called, to verify that V (E) really was zero. In each such case, we either got a floating point proof that V (E) ≠ 0 or an algebraic proof that V (E) = 0.

The next step was to compute a histogram for the values of R(E) = Log_{10} |V (E)| /length(E) for expressions of length 5 in expanded form, which were not zero, hop-

ing to see a nice familiar distribution. However, the result did not look like anything familiar, or nice, but on the contrary, remarkably recalcitrant, as can been seen in figure 1. This took 8384 seconds, using Maple 7 on a laptop. The large positive R(E) values come from natural numbers. The dominant expression of length 5 is a sequence of 5 nines. The negative R(E) values are more interesting. However, many of them are reciprocals of values which occurred with large positive ρ at the previous level. There are also a few negative ρ values at the very left of the histogram; it is these which represent a threat to the uniformity conjecture. There were 22 expressions with R value below -3/5.

A histogram of absolute values modulo 1, defining x modulo 1 to be x − floor(x) was also found. See figure 2, for length 5 results. The spikes represent many duplicate values of numbers which are represented by short expressions, such as 1/2 or exp(1).

It seemed possible that some underlying pattern might be masked by the large number of duplicate values which were being counted. However, removing the duplicates proved computationally difficult. The problem was that in each case in which a pair of expressions might define the same number, it was necessary, in order to avoid mistakes which would be fatal to the spirit of this investigation, to use simplify in Maple to check that the two numbers really were equal. Working with absolute values modulo 1 at length 5, the unique values should, hopefully, be fairly evenly spaced, with gaps at least 10^{−15}. The unit interval was divided into 10^{5} subintervals and the values ordered in a linked list in each subinterval. This many subintervals were used so that, hopefully, there would be more subintervals than unique values. Then, each time a new expression was obtained, the appropriate list was checked, to see if this was a new value. As part of this, the table data structure in Maple was used to give a source expression for each floating point value generated. Precision 20 was used.

Figure 1: Distribution of Logarithms / Length 10 Figure 2: Distribution of values mod 1

11

If we regard a floating point number as a code for an expression which generates it, the table would be a decoder. So it was always possible to go back to see where a number originated. In all cases in which it seemed that two numbers might be equal (i.e. if the floating point numbers agreed to at least 15 decimal places), Maple was asked, via the simplify procedure, for a proof that the two expressions were equivalent. In this case, although no counterexamples were found, there were some anomolies. There were three cases in which simplify failed to reduce to zero expressions which are actually equivalent to zero. One of these problem cases was:

|log(i(ilog(2) + π))|−floor(|log(i(ilog(2) + π))|−|log(−i(−ilog(2) + π))|+floor(|log(i(ilog(2) + π))|

and the other two were also of this form. The reason these are no longer length 5 expressions is that they have been through simplify at least once, and this sometimes increases length. In any case, this is not a counterexample, just a limitation of simplification in Maple 7.

We would say that the population was equi-distributed in [0, 1) if for any subinterval I, the number of real values at level k (reduced modulo 1 with duplicates removed) in I divided by the total number of real values at level k reduced modulo 1 with duplicates removed tends to the length of I, as k tends to infinity. We naively expected that the population would be equi-distributed in this sense, and that this would appear even at length

5. However, we got the following results for the length 5 absolute values modulo 1 with duplicates removed. See figure 3.

We do not see equi-distribution at this level. Of course we could still have equi-distribution in the limit, as length k tends to infinity.

There are some small numbers on the left hand end of this distribution. Suppose we put the unique absolute values of length 5 expressions modulo 1 into a list, List1_{1}. This list begins:

log(2981) − 8

log(8104) − 9

\sqrt{(}log(166)^{2} + π^{2}) − 6

log(8105) − 9

The gaps between these numbers were also computed and ordered into another list, List_{2}. These gaps are differences between absolute values of length 5 numbers modulo 1. Some of the gaps are very small. List_{2} begins:

75^{1/71} − 7^{1/32}, 89^{1/79} − e^{5/88}, 2^{1/665} − 3^{1/527}, ...

but there are still no counterexamples in this list.

It seems that the somewhat ominous crowding toward zero in the length 5 values modulo 1 with duplicates removed may be caused by relatively simple expressions, such as A/n, A^{1/n} −1, exp(A/n), Log(A/n)−1, where n is large.

In the rest of this paper, we look for counterexamples by examining simple expressions with parameters.

Figure 3: Distribution mod 1 with duplicates removed 13

6 Differences of logarithms and natural numbers

All the expressions of the form log(m) − n for n and m natural numbers give different values; so there are many chances to obtain small values, such as are found at the beginning of List_{1} mentioned above. On the other hand, these values are certainly not randomly distributed. For each m, there is only one good n to try, obtained by rounding the logarithm of m. A better way to find good pairs is to consider log(m) − n), where m is obtained by rounding exp(n), and n = 1, 2, .... This was done for values of n up to 10,000, computing at precision 10,000 in Maple. Each time a new maximum ρ(E) value was obtained, it was printed, giving the following table:

\begin{matrix}V alue of n & ρ(log(round(e^{n})) − n) \\ 1 & 0.25 \\ 3 & 0.47 \\ 8 & 0.69 \\ 19 & 0.75 \\ 45 & 0.88 \\ 75 & 0.93 \\ 135 & 0.95 \\ 178 & 0.96 \\ 209 & 0.97 \\ 732 & 0.99 \\ 1351 & 0.995 \\ 1907 & 0.996 \\ 5469 & 0.999 \end{matrix}

Note that the numbers here are not the same as those at the beginning of List_{1}, since we are rounding, rather than taking the floor. The question of how small a quantity |m − e^{n}| can be for n and m natural numbers and n not zero was first considered by K. Mahler. He proved a lower bound of exp(−40logn logm) in 1953; 14 years later he replaced 40 by 33; in 1973 M. Mignotte inproved the constant down to 17.7. Mahler conjectured the existence of an absolute constant c > 0 so that for m ≥ 2

|m − e^{n}| > m^{−c}.

All of this information comes from [Waldschmidt].

The results above suggest, at least for numbers of this form, a supremum of 1 (or a little above 1) for ρ in this case. This would imply Mahler’s conjecture, and give us a value for c.

The numbers found in the lower part of the first column of the table above are exponents of e which result in values which have good integral approximations. Any linear combination of these exponents with integral coefficients will give an exponent which will result in a value with a fairly good rational approximation: that is a linear combination of two powers of e with a small value. It is possible, in general, to obtain bounds for the number of simultaneous small values of linear forms of powers of e with integral coefficients. One approach is the following. Suppose V is a vector of powers of e, from zero to n. Let M be an (n + 1) by (n + 1) nonsingular matrix of integers so that MV = E is a small vector. Assume that E = [ϵ_{1}, …, ...ϵ_{(}n + 1)], with ϵ_{i} ≤ ϵ for all i. The determinant of M has absolute value at least 1. It follows, by Cramer’s rule, that:

e^{n} ≤ (n + 1)!Hϵ

where H is an upper bound on the absolute value of products of (n+1) integers in M, one from each row and one from each column. This does give a theoretical lower bound for ϵ; however, the results in the table are far above this lower bound.

7 Other methods of searching for counterexamples

In some cases, there are methods which allow looking deeper into the search space. Three such methods are continued fractions, the LLL algorithm, and the PSLQ algorithm. These methods can be used to find non zero integral coefficients c_{1}, …, c_{n} so that a linear form

λ = c_{1}a_{1} + ⋯ + c_{n}a_{n}

is small, where a_{1}, ..., a_{n} are computable real numbers.

The case of linear forms with two terms seems especially promising from the point of view of searching for a counterexample, since the form can be divided by the larger of the two coefficients without increasing the length. For this reason, the investigation has concentrated on linear forms in two terms. Essentially this reduces to finding good rational approximations to closed form numbers.

7.1 Good rational approximations

The constinued fraction construction for a real number x may be defined as follows. The first partial quotient of x is a_{0} = floor(x). The first error term is E_{0} = x − floor(x). We then define the sequence of partial quotients by a_{n+1} = floor(1/E_{n}), and E_{n+1} = 1/E_{n} − a_{n+1}, as long as E_{n} is not zero. The numbers in E will be called error values.

Assume that x is irrational. We let p_{0} = a_{0}, p_{1} = a_{1}a_{0} + 1, and p_{n} = a_{n}p_{n−1} + p_{n−2}. We let q_{0} = 1, q_{1} = a_{1}, and q_{n} = a_{n}q_{n−1} + q_{n−2}. The fraction p_{n}/q_{n} is called the nth convegent to x, and all of them are extremely good approximations. Note that the denominators, q_{n}, increase at least as rapidly as the Fibonacci sequence. We have :

p_{n}/q_{n} = a_{0} + 1/(a_{1} + 1/(a_{2} + 1/(a_{3} + .......... + 1/a_{n})))

Theorem 5. 1. 1/(q_{n}q_{n+2} < |p_{n}/q_{n} − x| < 1/(q_{n}q_{n+1}) < 1/(a_{n+1}q_{n}^{2})

2. p_{n}/q_{n} − p_{n−1}/q_{n−1} = (−1)^{n−1}/(q_{n−1}q_{n}

3. x − p_{n}/q_{n} = (−1)^{n}/(q_{n}/E_{n} + q_{n−1})

4. If |x − p/q| < 1/(2q^{2} then p/q is a convergent, i.e. is equal to p_{n}/q_{n} for some n

The proofs of the above can be found in [Hardy and Wright 1938]. If α is real we can look for good rational approximations to α by

searching for large partial quotient coefficients in the continued fraction expansion of α. In this way we might find counterexamples or near counterexamples to the Uniformity conjecture of the form α − p/q. Item (4) in the theorem above implies that if α − p/q is a counterexample to the uniformity conjecture, then p/q can be computed as a convergent.

Let C be some constant.

Lemma 2. Suppose α is a closed form number. If |α − p/q| < 10^{−C(length(p)+length(q)+2+length(α)}, then |α − p/q| < (1/q^{2})10^{−(2+length(α)+Log_{10}(α)+2(C−1)length(q))}.

Proof.

Suppose, without loss of generality, that α is positive. So p and q are also positive.

We have length(q) > Log_{10}(q), and length(p) > Log_{10}(p). Therefore |p/q − α| < 1/(100pq). It follows that Log_{10}(p) + 1/p^{2} > Log_{10}(q) + Log_{10}(α). In all cases, it is true that

length(p) ≥ Log_{10}(p) + 1/(p + 1). Therefore length(p) > Log_{10}(q) + Log_{10}(α). Thus

length(p) + length(q) + length(α) + 2 ≥ 2Log_{10}(q) + length(α) + Log_{10}(α) + 2, and the result of the lemma follows.

□

The lemma, and part (4) of the theorem above, implies that a counterexample to the uniformity conjecture in the form α − p/q would have p/q as a convergent, p_{n}/q_{n} for some n. Also the next partial quotient a_{n+1} must be very large. We expect a_{n+1} to be about 10^{(2+length(α)−|Log_{10}(α)|+2(C−1)length(q_{n}))}.

We note that, if C > 1, the set of real numbers x which have infinitely many partial quotients a_{n+1} larger than 10^{2(C−1)length(q_{n})} has measure 0. In that sense, finding such a large partial quotient might be considered surprising. We do expect, in general, that the supremum of the partial quotients will tend to infinity, but not very quickly.

It follows from the above that there will exist a dominant expression of the form α−p/q just if α has a partial quotient bigger than length(α)+ Log_{10}(α) + 2. So there will be a dominant expression if the sequence of partial quotients has a subsequence which increases linearly. This is not difficult to arrange. For example, the sequence of partial quotients for exp(1/1000) has a subsequence which increases by 2000 at every 3 steps. So there is a dominant expression of the form exp(1/1000) − p/q, and this can be found by iterating the continued fraction loop (3/2)10^{5} times. The resulting approximation to exp(1/1000) can be indicated but can not be written using a canonical fraction, due to size. In general, in the continued fraction of exp(1/k) the quotient q_{3n+1} = (k − 1) + 2nk. Note that since the sequence of demonimators, q_{n} increases exponentially, there can not be a counterexample to the uniformity conjecture in this form.

For α = A^{1/B}, with A and B natural numbers between 2 and 100, the first 50 partial quotients in the continued fraction representation of α were computed; and then the minimal index n with maximal partial quotient was found, and then p/q was taken to be the n − 1 st convergent. The following table shows all the values of irrational α for which −floor(Log_{10} | α−p/q |) > length(p)+length(q)+length(A)+length(B). Of course this condition would have to be satisfied by any counterexample.

\begin{matrix}α & length(q) & −floor(Log_{10} | α − p/q |) & index max quotient & max quotient \\ 2^{1/3} & 17 & 37 & 36 & 534 \\ 2^{1/8} & 3 & 9 & 6 & 761 \\ 2^{1/53} & 13 & 30 & 29 & 1909 \\ 4^{1/6} & 17 & 37 & 36 & 534 \\ 4^{1/75} & 14 & 32 & 32 & 22, 415 \\ 5^{1/64} & 21 & 46 & 36 & 1366 \\ 6^{1/41} & 7 & 18 & 17 & 2808 \\ 6^{1/87} & 6 & 16 & 12 & 3408 \\ 7^{1/8} & 6 & 15 & 13 & 3658 \\ 7^{1/42} & 31 & 66 & 49 & 1191 \\ 8^{1/9} & 17 & 37 & 36 & 534 \\ 8^{1/29} & 25 & 54 & 48 & 3291 \\ 8^{1/44} & 6 & 16 & 10 & 22, 459 \\ 8^{1/50} & 6 & 16 & 10 & 5335 \\ 9^{1/49} & 4 & 12 & 6 & 53319 \\ 9^{1/93} & 12 & 28 & 17 & 5183 \\ 10^{1/42} & 11 & 27 & 23 & 179, 496 \\ 12^{1/57} & 12 & 29 & 29 & 595590 \\ 14^{1/6} & 19 & 42 & 42 & 106, 587 \\ 20^{1/93} & 19 & 43 & 43 & 15135 \\ 30^{1/24} & 9 & 23 & 17 & 71229 \\ 47^{1/23} & 12 & 29 & 25 & 18132 \\ 50^{1/38} & 2 & 9 & 6 & 28626 \\ 55^{1/36} & 7 & 19 & 10 & 18930 \\ 59^{1/47} & 24 & 54 & 50 & 183938 \\ 68^{1/95} & 17 & 39 & 27 & 221647 \\ 74^{1/7} & 4 & 13 & 13 & 89350 \\ 84^{1/42} & 25 & 55 & 39 & 32347 \\ 89^{1/45} & 19 & 43 & 47 & 34559 \end{matrix}

As can be seen from the table, no counterexamples have been found in this way. The length of the maximal partial quotients can be estimated by subtracting twice column 2 from column 3.

Note that if λ = n^{1/m} − p/q is a counterexample to the uniformity conjecture, then λ ≠ 0 and | λ |< 1/N(k), where k = l(n) + l(m) + l(p) + l(q) + 3. Assuming we use decimal representation, N(k) > 10^{(1+ϵ)k} for some ϵ > 0.04. It follows from the Thue Siegel Roth theorem that | λ |> 10^{−(1+ϵ)(l(p)+l(q)} for all but finitely many rational p/q. We would like to have an effective version of the Thue Siegel Roth theorem which would give us a way to compute an upper bound on the denominator q from the number ϵ. If we had a way to compute such an upper bound, this would give us a bound on the number of partial quotients in the continued fraction expansion we need to examine to be sure of catching any counterexamples to the uniformity conjecture.

The above results also have some consequences for the abc conjecture, in the following form.

ABC conjecture Let a, b, c be relatively prime integers and assume a + b = c. Then for each positive δ > 0 there exists a constant C(δ) such that

Max(|a| , |b| , |c|) ≤ C(δ)sqf(abc)^{1+δ}

where sqf(n) means the product of the prime factors of n, taking each prime factor just once.

Let n^{1/m} −p/q = ϵ. Then q^{m}n = p^{m} +c, where c = (p+ϵ)^{m} −p^{m}). Let a = q^{m}n, b = p^{m}. We get sqf(abc) ≤ qnpc. So p^{n} ≤ C(δ)(qnpc)^{1+δ}. In this way we can get some numerical lower bounds on some C(δ), assuming the conjecture is true.

The above computations were done in Maple, and took days. The nice feature about using Maple here was that the errors (in the sequence E mentioned above) can be held symbolically, so that the only possible precision error in the computation of the quotient is at the last step, when the floor is taken. However, this was becomming impractical, and therefore it was decided to switch over to using C++, and and to compute the partial quotients entirely in floating point arithmetic, using the number theoretic library developed by Victor Shoup, [Shoup]. As would be expected, this was much faster.

For n from 2 to 100 and for m from 2 to 100, the first 200 partial quotients of n^{1/m} were computed. The maximal partial quotient was found in each case, using floating point arithmetic with precision 800. The partial quotients which were larger than 500,000 are recorded in the following table. It should be pointed out that not very much is known about the sequence of partial quotients for algebraic numbers. It is an open question as to whether or not the sequence of partial quotients is unbounded for any algebraic number. See [Baker 1975]. It is also not known whether or not all algebraic numbers with degree more than two have unbounded sequences of partial quotients.

\begin{matrix}Expression & Index of maximal Quotient & Maximal Quotient \\ 12^{1/57} & 29 & 595, 590 \\ 33^{1/18} & 197 & 701, 182 \\ 60^{1/60} & 135 & 3, 416, 745 \\ 90^{1/61} & 169 & 569, 447 \end{matrix}

This took about 6 minutes. Note that only one number occurs in both lists. When the computation was repeated with precision 100, the results were incorrect; the resulting list contained numbers which should not have been included and left out some of the numbers which should have been included. However, the mistakes went away when precision was increased to 200. The four results in the table have also been confirmed in Maple.

This computation was repeated, using precision 800, for expressions of the form log(n)^{1/m}, and log(n)∗log(m), and log(n/m), and log(n)/log(m) and log(n + log(m)), and exp(n/n + m), and log(n) ∗ exp(1/m), with the following results. (Expressions such as Log(91) ∗ Log(79) are not included if they are obviously numerically identical to expressions which are in the table.)

\begin{matrix}Expression & Index of maximal Quotient & Maximal Quotient \\ Log(11)^{1/82} & 168 & 1, 778, 374 \\ Log(15)^{1/46} & 123 & 922, 457 \\ Log(42)^{1/13} & 8 & 523, 196 \\ Log(44)^{1/78} & 178 & 1, 359, 414 \\ Log(70)^{1/52} & 67 & 910, 743 \\ Log(2) ∗ Log(79) & 143 & 1, 510, 024 \\ Log(4) ∗ Log(79) & 149 & 755, 011 \\ Log(7) ∗ Log(85) & 45 & 844, 533 \\ Log(8) ∗ Log(79) & 147 & 453, 074 \\ Log(26) ∗ Log(65) & 194 & 732, 087 \\ Log(49) ∗ Log(85) & 41 & 1, 689, 066 \\ Log(55) ∗ Log(93) & 4 & 512, 877 \\ Log(64) ∗ Log(79) & 147 & 2, 265, 036 \\ Log(84) ∗ Log(89) & 169 & 695, 866 \\ Log(85) ∗ Log(91) & 111 & 689, 759 \\ Log(86)/Log(31) & 24 & 652, 885 \\ Log(89)/Log(62) & 106 & 591, 077 \\ Log(90)/Log(72) & 36 & 564, 735 \\ Log(21) ∗ exp(1/70) & 8 & 993, 651 \\ Log(24) ∗ exp(1/96) & 129 & 597, 698 \\ Log(33) ∗ exp(1/27) & 105 & 3, 187, 001 \\ Log(40) ∗ exp(1/78) & 173 & 5, 786, 300 \\ Log(52) ∗ exp(1/4) & 47 & 977, 868 \\ Log(57) ∗ exp(1/42) & 62 & 737, 863 \\ Log(58) ∗ exp(1/71) & 170 & 2, 330, 275 \\ Log(40 + Log81)) & 96 & 677, 910 \\ Log(77 + Log55) & 143 & 805, 127 \\ exp(37/(37 + 92)) & 146 & 1, 734, 520 \\ exp(43/(43 + 3)) & 100 & 1, 595, 639 \\ exp(45/(45 + 34)) & 64 & 754, 664 \\ exp(51/(51 + 43)) & 125 & 4, 219, 484 \end{matrix}

There are no counterexamples or dominant expressions in this range. It does not seem possible safely to generalise about such results. Very roughly speaking, however, it seems that the size of the largest partial quotient found in these searches tends to be approximately proportional to the number of partial quotients computed.

8 Further work: Near Integer Relations

We may also search for counterexamples among linear forms in more than two terms, although this appears to be less promising. Methods which could be used for such a search are briefly discussed below.

If x is a vector of n real numbers, an integer relation for x is a non zero integer vector m so that xm^{T} = 0. A near integer relation is a non zero integer vector m so that xm^{T} has “small” absolute value.

We can make the notion of “small” precise if x consists of closed form numbers. Define length(x) to be the sum of the lengths of the components, considering these as closed form numbers. We will say that m is is a near integer relation for x if

|xm^{T} | < 10^{−(length(m)+length(x)+2n−1)}

These near integer relations include all possible counterexamples to the uniformity conjecture of the form xm^{T}.

For fixed x = (x_{1}, …, x_{n}), it is possible to search for such near integer relations using the LLL or PSLQ algorithm.

In order to apply the LLL algorithm we form a matrix A by replacing the last column of the n by n identity matrix by the transpose of (Mx_{1}, …, Mx_{n}), where M is some large number. Form the lattice L generated by the rows of this matrix. If m is a near linear relation,

λ = m_{1}x_{1} + ⋯ + m_{n}x_{n}

is small and (m_{1}, …, m_{n−1}, Mλ) is a short vector in the lattice.

Choosing various values of the multiplier M, we can obtain lower bounds of the sizes of non zero vectors in the lattice, and thus eliminate some parts of the search space for counterexamples. For details and some results, see [De Weger 1987] and [Richardson 2000].

Another approach to this problem is to use the PSLQ algorithm. See [Bailey]. Suppose we are looking for near linear relation m = (m_{1}, …, m_{n}) so that

λ = m_{1}x_{1} + ⋯ + m_{n}x_{n} and |λ| < ϵ.

Assume

1. ∑ length(m_{i}) = k

2. Maximum(length(m_{i})) ≤ k/n + d. This means that none of the coefficients are much longer than the average length.

3. ϵ = 10^{−(k+2n−1+length(x_{1})+···+length(x_{n}))}

xm^{T} = λ

10^{k/n} ≤ |m| ≤ 10^{k/n+d+1}

If there is an m satisfying these conditions, then there is a vector x^{∗} so that x^{∗}m^{T} = 0 and |x − x^{∗}| < ϵ/ |m| < ϵ10^{−k/n}. Suppose we work with precision ϵ. Use x to represent the hypothetical x^{∗}. Find a lower bound on |m| using the PSLQ algorithm. If we get |m| > \sqrt{n}10^{k/n+d+1}, we can conclude that there is no counterexample satisfying the above conditions.

If n is small, we can get stronger results.

Example 1. x = (1, 2^{1/997}, 2^{1/998}). λ = a + b2^{1/2} + c2^{1/3} = xm^{T}. As above, we assume that the sum of the lengths of a, b, c is k. The length of λ is then k + 14. We need to use precision

ϵ = 10^{−(k+14)}. For various values of k, we can use PSLQ to get lower bounds on |m|.

This was done from k = 3 to k = 100. For k = 3, the result is a lower bound on |m| with 10 digits length. For k = 100, a lower bound of 57 digits was obtained. The lower bound on |m| increased with slope about 1/2 with k. In all cases the lower bound on |m| had length exceeding k/2 + 6. Since a counterexample could not have just one large coefficient, (because λ must be small), this implies that there are no counterexamples with k ≤ 100.

The case x = (1, 2^{1/2}, 2^{1/3}) is similar, using precision 10^{−(k+10)}.

For n > 3 , the technique does not work so well. It only allows us to search for counterexamples among linear forms in which all the coefficients have approximately the same length.

Example 2. Consider

λ = a + b2^{1/2} + c2^{1/3} + d2^{1/4} + e2^{1/5} + f2^{1/6}

with m = (a, b, c, d, e, f) integral and non zero. As above, lower bounds on norms of possible near linear relations from k from 6 to 100 were found, using precision ϵ = 10^{−(k+20)}. As expected, these lower bounds on the norms had length larger than (k + 20)/5 in all cases. It follows that if there is a counterexample with k < 100, the largest coefficient must have length more than k/5 + 2.

These examples used a PSLQ procedure written in Maple by Simon Langley.

8.1 Discussion

For exp log expressions E in expanded form, which do not represent zero, we have a measure ρ(E) of smallness. A weak form of the uniformity conjecture claims that ρ(E) < C, for some constant C. It seems sensible to try to estimate the maximum value of ρ by computational experiment. However, by direct search among simple exp log expressions, we do not even find an expression E such that ρ(E) > 1. (We know that there exist expressions with this property.) It seems rather difficult to search in a direct way in the space of exp log functions. We have some good techniques for finding fairly small expressions in special cases, for example continued fractions and PSLQ. We also have some constructions which might be expected to produce new small expressions from an existing set: for example, if α is small, then e^{α} − 1 is also fairly small, as is Log(1 + α), as is f(α) where f is any function with a root at 0; also we expect that a random element of the ideal generated by small expressions may again be small. It may be that a good way to search for small expressions, or for counterexamples to the unformity conjecture, is to use some sort of evolutionalry computing. The idea would be to set up an environment in which the organisms were exp log expressions, and the measure of fitness would be ρ. Hopefully, evolution would produce small expressions. The examples produced in this way should throw some light on the many interesting open questions in the area of Diophantine Approximation.

9 References

References

[Bailey] Helaman R. P. Ferguson, David H. Bailey, and Steve Arno, Analysis of PSLQ, An Integer Relation Finding Algorithm, preprint. See www.nersc.gov/ dhb.

[Baker 1975] A. Baker, Transcendental number theory, CUP, 1975 [Chow 1999] T. Y. Chow, What is a Closed-Form Number?, Amer-

ican Mathematical Monthly, Vol 106, No 5, 1999, pp 440-448

[De Weger 1987] B. M. M. De Weger, Solving exponential Diophantine equations using lattice basis reduction algorithms, J. Number Theory 26 (1987) 325-367.

[Hardy and Wright 1938] , G.H. Hardy and E.M. Wright, An Introduction to the Theory of Numbers, Oxford, Clarendon press, 1938

[Hindry and Silverman 2000] M. Hindry and J. Silverman, Diophantine Geometry, An Introduction, Springer Graduate Texts in Mathematics, 2000

[Hlawka et al 1991] E. Hlawka, J. Schoissengeier, R. Taschner, Geometric

and Analytic Number Theory. Springer Verlag, 1991

[Lang 1966] S. Lang, Introduction to Transcendental Numbers,

Addison Wesley, 1966

[Philipon 1999] P. Philippon, Quelques remarques sur des questions d’approximation diophantine, Bull Austral. Math. Soc., Vol 59(2), (1999), pp 323-334.

[Philipon 2000] P. Philippon, Addendum a quelques remarques sur des questions d’approximation diophantine, Bull Austral. Math. Soc., vol 61(1), (2000), pp 167-169.

[Pohst 1997] M. Pohst, On Validated Computing in Algebraic Number Fields, J. Symbolic Computation 24, pp 657-666, 1997

[Richardson 1997] Daniel Richardson, How to Recognise Zero, J. Sym-

bolic Computation (1997), 24, pp 627-645

[Richardson 2001] Multiplicative Independence of Algebraic Numbers and Expressions, presented at Mega 2000, also in Journal of Pure and Applied Algebra 164, 2001, pp 231-245, ISSN 0022-4049

[Richardson 2000] Daniel Richardson, The Uniformity Conjecture, Proceedings of Computability and Complexity in Analysis, CCA2000, September 17-19, Swansea, Wales. Also in associated Springer lecture notes in comuter science Vol 2064, pp 253-272. See www.bath.ac.uk/ masdr/unif.dvi.

[Shoup] See http://www.shoup.ntl.net [Sprindzhuk 1980] V. G. Sprinkzhuk, Achievements and Problems in Dio-

phantine Approximation Theory, Russian Mathematical Surveys 35 (4), 1980, pp 1-80

[Van Der Hoeven 95] Joris van der Hoeven, Automatic Numerical Expansions, in J.-C. Bajard, D. Michelucci, J.-M. Moreau, and J.-M. Muller, editors, Proc. of the conference “Real numbers and computers”, Saint-Etienne, France, Pages 261-274, 1995 [Van Der Hoeven 97] Joris van der Hoeven, Automatic Asymptotics,

Ph.D. thesis, Ecole Polytechnique, 1997.

[Van Der Hoeven 2000] Joris Van Der Hoeven, Zero-testing, witness conjectures and differential diophantine approximation, Preprint

[Waldschmidt] Simultaneous approximation of numbers connected with the exponential function, J. Austral. Math. Soc., 25 (1978), 466-478